package com.hc.programming.tree;

import com.hc.programming.util.ArrayUtil;

import java.util.Arrays;

/**
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 一般来说，删除节点可分为两个步骤：
 * 1. 首先找到需要删除的节点；
 * 2. 如果找到了，删除它。
 * <p>
 * 示例 1:
 * <a href="./删除二叉搜索树中的节点-示例1.png">示例1</a>
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 * <a href="./删除二叉搜索树中的节点-示例1-图2.png">示例1-图2</a>
 * 示例 2:
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 * 解释: 二叉树不包含值为 0 的节点
 * 示例 3:
 * 输入: root = [], key = 0
 * 输出: []
 * <p>
 * 提示:
 * 节点数的范围 [0, 10^4].
 * -10^5 <= Node.val <= 10^5
 * 节点值唯一
 * root 是合法的二叉搜索树
 * -10^5 <= key <= 10^5
 * <p>
 * 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/16 22:29
 */
public class 删除二叉搜索树中的节点 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{5,3,6,2,4,null,7};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=,--" + deleteNode(tree, 3));
        arr = new Integer[]{5,3,6,2,4,null,7};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=,--" + ArrayUtil.toString(deleteNode(tree, 0)));
        arr = new Integer[]{};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=,--" + ArrayUtil.toString(deleteNode(tree, 0)));
    }
    public static TreeNode deleteNode(TreeNode root, int key) {
        return 递归删除(root, key);
    }

    /**
     * 方案1：找到节点后，将右子树中最小的节点，挪到当前位置
     */
    private static TreeNode 递归删除(TreeNode root, int key) {
        if (root == null) return null;
        if (key < root.val) root.left = 递归删除(root.left, key);
        else if (key > root.val) root.right = 递归删除(root.right, key);
        else {
            // 找到了需要删除的节点
            // 子节点为空，直接删除
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            // 左右子树都不为空，找到右子树最小节点
            TreeNode minNode = root.right;
            TreeNode pre = null;
            while (minNode.left != null) {
                pre = minNode;
                minNode = minNode.left;
            }
            // 右子树最小节点替换当前节点
            if (pre != null) pre.left = minNode.right;
            if (minNode != root.right) minNode.right = root.right;
            minNode.left = root.left;
            return minNode;
        }
        return root;
    }
}
